﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <iomanip>
#include <unordered_map>

using namespace std;
/*
实现一个栈，两个 API：push(x) 和 pop()，push 是正常 push，但 pop 时需要返回出现频度最高的数，如果有多个频度同样最高的数，
返回离栈顶最近的那个 (不限定语言)
    ```
    FreqStack = new FreqStack();
    freqStack.push (5); //  堆栈为 [5]
    freqStack.push (7); //  堆栈是 [5,7]
    freqStack.push (5); //  堆栈是 [5,7,5]
    freqStack.push (7); //  堆栈是 [5,7,5,7]
    freqStack.push (4); //  堆栈是 [5,7,5,7,4]
    freqStack.push (5); //  堆栈是 [5,7,5,7,4,5]
    freqStack.pop ();   //  返回 5 ，因为 5 出现频率最高。堆栈变成 [5,7,5,7,4]。
    freqStack.pop ();   //  返回 7 ，因为 5 和 7 出现频率最高，但7最接近顶部。堆栈变成 [5,7,5,4]。
    freqStack.pop ();   //  返回 5 ，因为 5 出现频率最高。堆栈变成 [5,7,4]。
    freqStack.pop ();   //  返回 4 ，因为 4, 5 和 7 出现频率最高，但 4 是最接近顶部的。堆栈变成 [5,7]。
*/


class My_stack {
public:
	My_stack():size(0){}
	void push(int x)
	{
		arr.push_back(x);
		size++;
		mp[x]++;
	}

	int pop()
	{
		int max = -1;
		int num = 0;
		int index = 0;
		for (int i = size - 1; i >= 0; i--)
		{
			if (mp[arr[i]] > max)
			{
				index = i;
				num = arr[i];
				max = mp[arr[i]];
			}
		}

		arr.erase(arr.begin() + index);
		mp[num]--;
		size--;
		return num;
	}

private:
	unordered_map<int, int> mp;
	vector<int> arr;
	size_t size;
};


int main()
{
	My_stack st;
	st.push(5);
	st.push(7);
	st.push(5);
	st.push(7);
	st.push(4);
	st.push(5);

	cout << st.pop() << endl;
	cout << st.pop() << endl;
	cout << st.pop() << endl;
	cout << st.pop() << endl;
	return 0;
}